package com.zh.note.leetcode.string;

import java.util.Arrays;

/**
 * 459. 重复的子字符串
 * <p>
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abab"
 * 输出: true
 * 解释: 可由子串 "ab" 重复两次构成。
 */
public class LC_459_repeatedSubstringPattern {

    public static void getNext(int[] next, String s) {
        char[] chars = s.toCharArray();
        // j前缀末尾，i表示后缀末尾
        int j = 0;
        next[0] = 0;

        for (int i = 1; i < chars.length; i++) {
            // 前后缀不相同的情况
            while (j > 0 && chars[i] != chars[j]) {
                // 遇到重复看前一位
                j = next[j - 1];
            }
            // 前后缀相同的情况
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    // public boolean repeatedSubstringPattern(String s) {
    //     String temp = s + s;
    //     // 去掉首尾字符
    //     temp = temp.substring(1, temp.length() - 1);
    //     // 判断去掉首尾字符后是否包含s
    //     if (temp.indexOf(s) > -1) {
    //         return true;
    //     }
    //     return false;
    // }
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() == 0) {
            return false;
        }
        int[] next = new int[s.length()];
        getNext(next, s);
        int len = s.length();
        if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String s = "aabaaf";
        int[] next = new int[s.length()];
        getNext(next, s);
        System.out.println(Arrays.toString(next));
    }
}
